package com.itheima.algorithm.dynamicprogramming;

import java.util.Arrays;

/**
 * <h3>打家劫舍 - 动态规划</h3>
 */
public class HouseRobberLeetcode198 {

    public static void main(String[] args) {
        HouseRobberLeetcode198 houseRobberLeetcode198 = new HouseRobberLeetcode198();
        System.out.println(houseRobberLeetcode198.rob(new int[]{2, 7, 9, 3, 1}));
    }

    /*
        价值  0   1   2   3   4
             0   0   0   0   0
        0(2) 2   0   0   0   0
        1(7) 2   7   0   0   0
        2(9) 2   7   11  0   0
        3(3) 2   7   11  11  0
        4(1) 2   7   11  11  12

        dp[4] = dp[2]+1 = 12
        dp[3] = max(dp[1]+3, dp[2]) = 11
     */
    public int rob(int[] nums) {
        if (1 == nums.length) {
            return nums[0];
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Integer.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Integer.max(dp[i - 1], dp[i - 2] + nums[i]);
            System.out.println(Arrays.toString(dp));
        }
        return dp[nums.length - 1];
    }
}
